package Algorithms.math;

/**
 * description: <br>
 * createTime: 2019/3/116:03 <br>
 *
 * @author zzh
 */
public class MathIssues {

    /**
     * Method Name：
     * Method Description: 用快速幂取模计算(a^b) %c<br>
     *
     * @param a 底
     * @param b 乘方数
     * @param c 取余数
     * @return 计算结果
     * <p>creator：zhihui.zhou
     * <p>createTime：2019/3/1 16:04
     */
    public static int calc(int a, int b, int c) {
        int ans = 1;   //记录结果
        a = a % c;   //预处理，使得a处于c的数据范围之下
        while (b != 0) {
            if ((b & 1) == 1) { //1即是0000000000000001，判断个位是否是1.如果b的二进制位是1，那么我们的结果是要参与运算的
                ans = (ans * a) % c;
            }
            b >>= 1;    //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位
            a = (a * a) % c;   //不断的加倍
        }
        return ans;
    }


    public static void main(String[] args) {
        long start = System.nanoTime();
        System.out.println(calc(9, 16, 10));
        System.out.println((System.nanoTime() - start));

        start = System.nanoTime();
        System.out.println(Math.pow(9, 16) % 10);
        System.out.println((System.nanoTime() - start));
    }
}
